// 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

// 百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

// 来源：力扣（LeetCode）
// 链接：https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree
// 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

#include<bits/stdc++.h>
#include<string>
#include<vector>
#include<unordered_set>
#include<unordered_map>
#include<set>
#include<queue>
using namespace std;

// 执行用时：
// 16 ms
// , 在所有 C++ 提交中击败了
// 79.70%
// 的用户
// 内存消耗：
// 14.1 MB
// , 在所有 C++ 提交中击败了
// 23.62%
// 的用户

  struct TreeNode {
      int val;
      TreeNode *left;
      TreeNode *right;
      TreeNode(int x) : val(x), left(NULL), right(NULL) {}
  };

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        TreeNode* res = dfs(root,p,q);
        return res;
    }
    TreeNode* dfs(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(root == p || root == q){
            if(dfs(root->left,p,q)!=NULL ||dfs(root->right,p,q)!=NULL){
                return root;
            }
            else{
                return root;
            }
        }
        else if(root == NULL){
            return NULL;
        }
        else{
            TreeNode* l = dfs(root->left,p,q);
            TreeNode* r = dfs(root->right,p,q);
            if(l != NULL && r!=NULL){
                return root;
            }
            else if(l !=NULL){
                return l;
            }
            else if(r!=NULL){
                return r;
            }
            else{
                return NULL;
            }
        }
    }
};